#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define NULL ((void *)0)


// 提示：32位系统4字节对齐，64位系统8字节对齐

// 定义数据部分的结构体
typedef struct
{
    char string[11];
    char num;
} DATA;

// 定义节点部分的结构体
typedef struct node
{
    DATA data;
    struct node *next;
} NODE;

typedef NODE *list;

// 添加一个节点
// *plist：链表的头节点
// data：添加节点的数据
// 返回：0表示添加失败，1表示添加成功
bool list_append(list *plist, DATA data)
{
    NODE *scan = *plist;
    NODE *pnew = (NODE *)malloc(sizeof(NODE));
    // 判断分配内存是否成功，失败直接返回
    if (pnew == NULL)
    {
        return false;
    }

    pnew->data = data;
    pnew->next = NULL;

    // 如果头节点为空，则直接指向新节点
    if (scan == NULL)
    {
        *plist = pnew;
    }
    // 否则令末尾节点的下一节点指向新节点
    else
    {
        while (scan->next != NULL)
        {
            scan = scan->next;
        }
        scan->next = pnew;
    }
    return true;
}

// 根据索引读取链表数据
// plist：链表
// index：索引
// 返回：链表对应索引的数据
DATA list_read(list plist, unsigned char index)
{
    unsigned char i;
    for(i=0;i<index;i++)
    {
        plist = plist->next;
    }
    return plist->data;
}

// 根据索引弹出链表节点并返回弹出节点的指针
// plist：链表
// index：索引
// 返回：弹出的节点的指针
NODE * list_pop(list *plist,unsigned char index)
{
    unsigned char i;
    NODE *result;
    NODE *scan = *plist;

    // 当 index=0 时，直接让头指针指向下一节点
    if(index == 0)
    {
        result = *plist;
        *plist = (*plist)->next;
        return result;
    }

    // 扫描到弹出节点的上一个节点
    for(i=1;i<index;i++)
    {
        scan = scan->next;
    }
    result = scan->next;
    scan->next = scan->next->next;
    return result;
}

// 根据索引删除链表节点
// plist：链表
// index：索引
void list_remove(list *plist, unsigned char index)
{
    free(list_pop(plist,index));
}

// 根据索引修改链表数据
// plist：链表
// index：索引
// data：修改后的数据
void list_modify(list plist, unsigned char index, DATA data)
{
    unsigned char i;
    for (i=0;i<index;i++)
    {
        plist = plist->next;
    }
    plist->data = data;
}

int list_find(list plist, DATA *data)
{
    unsigned char i;
    for(i=0;plist != NULL;i++)
    {
        if (memcmp(plist, data, sizeof(DATA)) == 0)
        {
            return i;
        }
        plist = plist->next;
    }
    return -1;
}


// 插入一个节点
// *plist：链表的头节点
// index：插入节点的位置索引
// data：插入节点的数据
// 返回：0表示添加失败，1表示添加成功
bool list_insert(list *plist, unsigned char index, DATA data)
{
    unsigned char i;

    NODE *scan = *plist;
    NODE *pnew = (NODE *)malloc(sizeof(NODE));
    // 判断分配内存是否成功，失败直接返回
    if (pnew == NULL)
    {
        return false;
    }

    pnew->data = data;

    // 当 index=0 时，直接让头指针指向下一节点
    if (index == 0)
    {
        pnew->next = *plist;
        *plist = pnew;
        return true;
    }

    // 扫描到弹出节点的上一个节点
    for(i = 1;i<index;i++)
    {
        scan = scan->next;
    }
    pnew->next = scan->next;
    scan->next = pnew;
    return true;
}

void list_clear(list *plist)
{
    NODE * p;
    while (*plist != NULL)
    {
        p = (*plist)->next; // 保存下一个节点的地址
        free(*plist);           // 释放当前节点
        *plist = p;         // 前进至下一个节点
    }
}

// TODO 可有可无
// 以十六进制的方式打印内存
// *p：欲打印内存指针
// size：打印大小 单位：1字节
void printmem(void *p,unsigned char size)
{
    unsigned char i,output;
    for(i=0;i<size;i++)
    {
        output = *((char *)(p+i));
        if(output < 10)
        {
            printf("0%x ",output);
        }
        else
        {
            printf("%x ",output);
        }
    }
    puts("");
}

// TODO 测试用
// 打印链表内容
// plist：链表
void printlist(list plist)
{
    unsigned char i;
    if(plist == NULL)
    {
        puts("该链表为空。");
    }
    else
    {
        for(i=0;plist != NULL;i++)
        {
            printf("%d | %s\n", plist->data.num, plist->data.string);
            plist = plist->next;
        }
    }

}


